Fault Tolerance for Outputs and Clients
Learn how to generate outputs with fault tolerance from state machine replicas and protect them from faulty clients.
We have already discussed how to make a group of state machines tolerant to faults. However, the output of the state machines goes to the output devices read by the voter devices. The output and voter devices can also fail. In this lesson, we will discuss how to deal with such failures.
Fault-tolerant outputs#
If we use a single output device for an ensemble of replicas, the resulting system would not be
1 of 2
2 of 2
Outputting externally#
A major proportion of applications of state machine replication requires outputting to a client, system, or node not part of the group of replicas. Suppose a system of replicated state machines has an output node that collects outputs from all replicas and sends the combined output to its destination. In that case, failure of the output node will result in the system generating incorrect outputs. Therefore, we must develop a solution enabling a system to tolerate faulty output devices.
We could replicate the output node to avoid the problem mentioned above. This replication can be done when every output node combines the output of all state machine replicas and sends its output to a stream or channel where all output nodes send their outputs.
If output nodes can exhibit Byzantine failures, then the output generated by a majority of
Outputting inside the system#
Suppose any component inside the system has to receive the output, such as a client. In that case, it should wait for identical replies from
Note: The basic tenet to tolerate failures relies on replication and then carefully picking the output.
Fault-tolerant clients#
Implementing a
Replicating the client#
One way to avoid faulty clients is replicating them to have multiple clients that fail independently. For an
Requests sent out by client replicas for a single request will not be the same. They will have different unique identifiers, and requests might have different content when the client has not been replicated as a state machine. For example, if a client requests by reading off some time-sensitive sensor, its replicas might make different requests. We will discuss both of these cases.
In the first case, when corresponding requests from client replicas can only differ in their unique identifier, we must improve our state machine model so that state machines receive
If clients can exhibit Byzantine failures, then a
fault-tolerant client will require replicas, and will execute the command after it receives its request from client replicas. For fail-stop failures, a
fault-tolerant client will have replicas; the first request received from any replica is sufficient for to execute the command.
Handling the case where client replica requests can vary in terms of their content requires using the application's workings. The objective is to ensure that our state machine executes a single command after receiving one or more client replica requests while maintaining fault tolerance.
For example, let’s look at our previous example of a client that reads from a sensor. When receiving client requests with different sensor values, the state machine could process a request with a median of values it received. Now, if Byzantine failures are possible,
Point to ponder
Question
Is taking the median of the client values a generic solution?
No, taking the median is an application-specific solution. This means each use case will need its own way to deal with possibly faulty client values.
Defensive programming#
There are circumstances when we cannot replicate clients. This may be because of a lack of hardware, or the application might be designed in a way that its clients cannot be replicated. In this situation, we must modify our state machine to minimize the effect of requests from faulty clients.
For instance, in our memory example, a client can write to all locations of the memory. A faulty client could overwrite in all locations and potentially destroy all information. We can limit write requests from clients so that they can only write to certain locations.
One way to avoid the effects of faulty clients is to include tests in commands. These tests are of the validity of requests, and if requests fail such tests, the pertinent client can be deemed faulty.
Let's consider our mutex example. The mutex state machine will execute a release command from any client, even the one not accessing the resource. Only the client with current access to the resource should be able to release the resource. We could have our mutex ignore release commands from other clients. Here is the updated release command:
It is also possible for a faulty client to acquire the resource and refuse to release it, i.e., not issuing the release command. We will need to limit the duration for which a client can access the resource. With a time limit, we can schedule a release within the acquire command. We will implement the timeout by scheduling a request for the state machine with a greater unique identifier so that the request becomes stable sometime in the future. Such a command does not need to be sent to other replicas since they will schedule it themselves. Let’s update the mutex command so that acquire automatically schedules a release of the resource:
The schedule(command, time) function assigns a unique identifier to the command to become stable after time amount of time has passed. This is done by assigning a unique identifier to command that is time greater than the unique identifier of the command from where schedule is called. Here, schedule assigns the command mutex.timeout(time_granted) a unique identifier B greater than the unique identifier of the current acquire command from where schedule is being called. Also, note that a resource can be released by either the client that has current access to the resource or by timeout.
Point to ponder
Question
Can you think of a better strategy for a timeout-based mutex?
It is not always possible for a computation to ensure that its computation will complete in a bounded time. The challenges include shared processors by multiple processes, a highly loaded node, or a slow component such as a disk, etc.
Sudden eviction of a process from a mutex might be disruptive. To address this, we can use the concepts of leases, where a process can extend the timeout some finite number of times before ending the process lease (we can achieve such a mechanism using lock services like Chubby or ZooKeeper). Lease-based mutexes might provide a better experience for developers compared to plain timeouts.
What's next?#
In the next lesson, we will discuss how to replace faulty replicas with non-faulty replicas.
Ordering Requests: Part II
Protocols for Maintaining Fault Tolerance: Part I